/*
 * ReverseFactor.cpp
 *
 *  Created on: 01-09-2013
 *      Author: Krzychu
 */

#include "ReverseFactor.h"

#include "Config.h"

#define ASIZE 255

ReverseFactor::ReverseFactor()
{

}

ReverseFactor::~ReverseFactor()
{

}

std::string ReverseFactor::getName()
{
	return "Reverse Factor";
}

void ReverseFactor::buildSuffixAutomaton(std::string pattern, SuffixAutomaton* aut)
{
	int patternSize = pattern.size();

	int p, q, r;
	char c;

	int init = aut->getInitial();
	int art = aut->newVertex();
	aut->setSuffixLink(init, art);
	int last = init;
	for (int i = 0; i < patternSize; ++i)
	{
		c = pattern[i];
		p = last;
		q = aut->newVertex();
		aut->setLength(q, aut->getLength(p) + 1);
		aut->setPosition(q, aut->getPosition(p) + 1);
		while (p != init && aut->getTarget(p, c) == aut->getUndefined())
		{
			aut->setTarget(p, c, q);
			aut->setShift(p, c, aut->getPosition(q) - aut->getPosition(p) - 1);
			p = aut->getSuffixLink(p);
		}
		if (aut->getTarget(p, c) == aut->getUndefined())
		{
			aut->setTarget(init, c, q);
			aut->setShift(init, c,
					aut->getPosition(q) - aut->getPosition(init) - 1);
			aut->setSuffixLink(q, init);
		}
		else if (aut->getLength(p) + 1 == aut->getLength(aut->getTarget(p, c)))
			aut->setSuffixLink(q, aut->getTarget(p, c));
		else
		{
			r = aut->newVertex();
			aut->copyVertex(r, aut->getTarget(p, c));
			aut->setLength(r, aut->getLength(p) + 1);
			aut->setSuffixLink(aut->getTarget(p, c), r);
			aut->setSuffixLink(q, r);
			while (p != art
					&& aut->getLength(aut->getTarget(p, c)) >= aut->getLength(r))
			{
				aut->setShift(
						p,
						c,
						aut->getPosition(aut->getTarget(p, c))
								- aut->getPosition(p) - 1);
				aut->setTarget(p, c, r);
				p = aut->getSuffixLink(p);
			}
		}
		last = q;
	}
	aut->setTerminal(last);
	while (last != init)
	{
		last = aut->getSuffixLink(last);
		aut->setTerminal(last);
	}
}

std::string ReverseFactor::reverse(std::string pattern)
{
	std::string result(pattern);
	int patternSize = pattern.size();

	for (int i = 0; i < patternSize; ++i)
	{
		result[i] = pattern[patternSize - 1 - i];
	}
	result[patternSize] = '\0';

	return result;
}

searchResult ReverseFactor::execute(std::string text, std::string pattern)
{
	searchResult result;
	result.iterationsTaken = 0;

	int textSize = text.size();
	int patternSize = pattern.size();

	int i, j, shift, period, init, state;
	SuffixAutomaton* aut = new SuffixAutomaton(2 * (patternSize + 2), 2 * (patternSize + 2) * ASIZE);
	std::string patternReversed = reverse(pattern);

	/* Preprocessing */
	buildSuffixAutomaton(patternReversed, aut);
	init = aut->getInitial();
	period = patternSize;

	/* Searching */
	j = 0;
	while (j <= textSize - patternSize)
	{
		result.iterationsTaken++;
		i = patternSize - 1;
		state = init;
		shift = patternSize;
		while (i + j >= 0 && aut->getTarget(state, text[i + j]) != aut->getUndefined())
		{
			state = aut->getTarget(state, text[i + j]);
			if (aut->isTerminal(state))
			{
				period = shift;
				shift = i;
			}
			--i;
		}
		if (i < 0)
		{
			result.positionsFound.push_back(j);
			if (Config::getInstance()->getFindOneOccurence())
			{
				return result;
			}

			shift = period;
		}
		j += shift;
	}

	return result;
}

